\chapter{Reti Complesse}
Le {\bf Reti complesse} hanno una topologia molto complessa, per questo motivo
lo studio ne ha risentito ed è progredito lentamente, infatti mancavano le
capacità computazionali e strumenti matematici per poterle studiare.\\
La struttura della rete può influenzare il comportamento e la dinamica della
stessa. All'interno di una rete non esiste un evento locale,  infatti questo 
può avere degi effetti sul resto della rete (per esempio black-out dovuto al
failure di un peer in una rete Ring).\\\\
Il Web è un primo esempio di rete complessa, il grafo risultante è orientato e
tramite la struttura delle pagine e alle connessioni tra queste ha reso
possibile il successo {\bf PageRank}, il primo algoritmo sviluppato da Page ed
utilizzato da Google per effettuare una valutazione delle pagine come risposta
delle query del motore di ricerca.\insertImage{1}{complex_network_WEB.png}{La
rete Web}\\\\
Al conrario la rete Internet è data dalla connessione fisica dei vari router.\\
La rete Internet è stata sviluppata per essere tollerante ai guasti, anche in
caso di attacco nucleare, per questo motivo il numero di black-out avvenuti sono
stati veramente pochi, uno per esempio è avvenuto dopo l'attacco alle Twins
Tower l'11 settembre 2001 dovuto al crollo delle torri che contenevano server
DNS.\\
TODO: Inserire varie tipologie  viste a lezione.

\section{Grafi}

Un grafo è un insieme di {bf\ Nodi o Vertici} che possono essere collegati tra
di loro tramite {\bf Archi}. \\\\
I grafi si suddividono in:
\begin{itemize}
\item {\bf Grafi orientati}: gli archi hanno un verso. In questo caso il primo
nodo si definisce {\bf uscente} e il secondo {\bf entrante}.
\item {\bf Grafi non orientati}: gli archi non hanno un verso e quindi non vi
possono essere più archi che collegano li stessi nodi.
\end{itemize}

\begin{itemize}
\section {Terminologia}
\item {\bf Loop} o {\bf Cappio}: un arco che collega un nodo a se stesso.
\item {\bf Incidente}: si definisce incidente su due nodi l'arco che collega
tali nodi.
{\bf Adiacente} o {\bf Vicino}: un nodo collegato tramite un arco ad un'altro
nodo.
\item {\bf Grado di un nodo}: il numero di archi incidenti da un determinato
nodo.
\item {\bf Grado uscente di un nodo}: il numero di archi uscenti da un
determinato nodo.
\item {\bf Grado entrante di un nodo}: il numero di archi entranti da un
determinato nodo.
\item {\bf Cammino} o {\bf Path}: una sequenza di nodi, ognuno adiacente al
successivo.Se contiene solo un nodo si definisce {\bf Degenere o Nullo}
\item {\bf Lunghezza di un cammino}: il numero di archi che contiene un cammino
o il numero dei nodi meno 1.
\item{\bf Diametro}: il più lungo di tutti i cammini minimi.
\item {\bf Ciclo semplice}: cammino non nullo in cui il primo e l'ultimo nodo
coincidono.
\item {\bf Grago aciclico}: un grafo privo di cicli, se è orientato a volte
viene definito {\bf DAG( directed acyclic graph)}
\item {\bf Grafo non orientato connesso}: grafo in cui ogni nodo è raggiungibile
da ogni altro nodo.
\item {\bf Grafo orientato fortemente connesso}: se ogni nodo è raggiungibile da
dogni altro nodo.
\item {\bf Grafo orientato debolmente connesso}: se considerando il grafo non
orientato corrispondente questo risulti essere connesso.
\item {\bf Sottografo}: grafo che si ottiene non considerando degli arci e/o dei
nodi con i relativi archi incidenti. Il sottografo può essere {\bf indotto} se è
costituito da alcuni nodi e dagli archi incidenti su di essi.
\item {\bf Grafo Pesato}: se ad ogni arco viene associato un peso.
\item {\bf Componenti Giganti}, solitamente un grafo contiene una sola
componente gigante, infatti la presenza di due componenti gigante può avere
effetti disastrosi (esempio nella scoperta dell'America nativi americani e
conquistatori rappresentano due Componenti Giganti).
\end{itemize}

\section{Network Analysis}
Vi sono alcune importanti proprietà in un rete che vengono studiate dalla {\bf
Network Analysis} su tre livelli diversi:
\begin{itemize}
\item {\bf Element-level analysis}:ricerc ai nodi più importanti all'interno
della rete
\item {\bf Group-level analysis}: definirsce e trova gruppi di nodi all'interno
della rete.
\item {\bf Network-level analysis}: studia le proprietà topologiche dell'intera
rete.
\end{itemize}
Nello studio Element-Level risulta molto importante studiare:
\begin{itemize}
\item L'importanza che ha un nodo o di un area all'interno di una rete.
\item La distanza fra nodi o aree.
\item Il grado di coesione di un'area di una rete
\item Le comunità di una rete.
\end{itemize}

\section{Element-Level Analysis}
\subsection{Grado di un nodo}

Una prima stima di centralità è data dal {\bf Grado di un nodo o Degree} che
consiste nel numero di archi uscenti, {\bf Outdegree} e archi entranti, {\bf
Indegree}, di un nodo. Il Grado di un nodo è una stima della capacità
relazionale del nodo all'interno della rete.

\subsection{Closeness Centrality}
La {\bf Closeness Centrality} è una misura della distanza media di un nodo da
tutti gli altri nodi utilizzando il calcolo dei cammini minimi, se non presente
si usa n.\\
Per ogni nodo la Closeness vale: 
\insertFrac{ c_{i} }{n-i}{\sum_{j\neq i} d(i,j) }
Il valore è compreso tra [0,1], dove un valore vicino allo 0 rappresenta un nodo
altamente isolato, metre vicino a 1 un nodo con molti cammini minimi verso gli
altri nodi.

\subsection{Betweenness Centrality}
La {\bf Betweenness Centrality} misura la centralità di un nodo contando i
cammini minimi tra gli altri nodi che lo contengono.\\
Per ogni nodo la Betweenness Centrality vale:
\insertFracWithMult{b_{i}}{\sum_{x,y}}{\sigma_{xy}(i)}{\sigma_{xy}}

Se un nodo ha un valore molto alto, allora questo ha un ruolo molto importante
nella rete e può essere visto anche come un punto debole della rete, attaccando
quel nodo si comprometterebbero le prestazioni della rete.

\section{Group-Level Analysis}
\subsection {Clustering}
Il {\bf Clustering} consiste nel cercare all'interno di una rete delle comunità,
una topologia di rete con un coefficiente di clustering massimo è la topologia
di rete {\bf Interamente Connessa}, infatti tutti i peer che compongono la rete
sono strettamente collegati tra di loro formando così una comunità.
\insertImage{1}{complex_network_CLUSTERING.png}{Clustering in un social network}
Esistono due tipologie di legami all'interno della rete:
\begin{itemize}
\item {\bf Legami Forti} che collegano nodi vicini all'interno della rete
\item {\bf Legami debole} che collegano nodi "distanti", o facenti parte di
comunità diverse, che garantiscono la struttura globale della rete.
\end{itemize}
Esistono inoltre divese stime di clustering: 
\begin{itemize}
\item {\bf Global Clustering} che rappresenta fornisce un'indicazione del
clustering dell'intera rete ed è rappresentato dalla seguente formula:
\insertFrac{C_{1}(G)}{3*\text{numero di triangoli in G}}{\text{numero di triple
connesse in G}}
\insertImage{1}{complex_network_GLOBAL_CLUSTERING_EXAMPLE.png}
{Esempio di clustering globale in cui C$_{1}$(G)=$\frac{3*1}{8}$= 0.375}
Il valore 3 a numeratore funge da valore di normalizzazione, in modo tale da
mantenere il valore del clustering compreso tra [0,1].

\item {\bf Local Clustering} che fornisce informazioni su quanto un nodo i e i
suoi vicini formano una {\bf Clique}, cioè un grafo completo. La formula che
definisce questo tipo di clustering è la seguente:
\insertFrac{C_{i}}{\text{numero di triangoli centrati in un nodo
i}}{\text{numero di triple connesse centrate in un nodo i}}
\\
A partire da un nodo i viene estratto il sottografo $G_i$ prendendo i primi
vicini di i, se i ha grado $K_i$ ci saranno $K_i$ vicini e pertanto nel grafo si
avranno $n_i=K_i+1$ nodi nel grafo.
In un grafo completo come questo è possibile avere un numero di archi al massimo
pari a \insertFrac{N_a}{n_1*(n_i-1)}{2}
\\
Un altro modo per calcolare $c_i$ può essere fare il rapporto tra gli archi
presenti in $G_i$ rispetto al numero di archi che potrebbero potenzialmente
esserci.\\
\\
Si può calcolare il coefficiente di clustering per l'intera rete come media di
tutti i coefficienti $c_i$ per tutti i nodi del grafo:
\insertFrac{C_{2}(G)}{\sum_{i}c_i}{n}

\end{itemize}



\section{Reti complesse}
Per comprendere le reti complesse c'è bisogno di strumenti matematici nuovi,
spesso si usano delle proprietà statistiche per l'analisi di questo tipo di
reti.
\subsection{Random Graphs (Erdos-Renyi)}
La generazione del grafo proposto da Erdos e Renyi segue un processo di tipo
democratico in cui ogni nodo ha una probabilità di essere connesso ad altri nodi
uguale a quella degli altri, l'evoluzione di questi grafi inizia a partire da
nodi isolati che sono selezionati e connessi ad altri nodi se questo è
possibile.
I parametri per la costruzione del grafo sono:
\begin{itemize}
\item {\bf n} il numero di nodi del grafo
\item {\bf p} un valore di probabilità tale che $0 \leq p \leq 1$. Per ogni
coppia di nodi i,j si aggiunge un nodo che li unisce con probabilità {\bf p}.
\end{itemize}
Per valori di p tendenti a 0 i nodi sono isolati, al contrario quando p tende a
1 i nodi tenderanno ad essere connessi con tutti gli altri. Per valori di n, il
grado medio dei nodi è $c = (n-1)*p$ e la distribuzione è approssimata con una
Poissoniana.
Per ogni nodo il numeo medio di archi può essere calcolato come la probabilità
di avere un arco moltiplicato per il numero di nodi, cioè $p*n$.
\\
Nei grafi random la probabilità che due nodi siano collegati è la stessa per
tutti i nodi, e il coefficiente di clustering è stato calcolato come
$\frac{c}{n-1}$.
Questo valore tende a 0 per valori grandi di n, ed è minore del valore che in
genere ci si aspetta in molte reti reali. Inoltre questo tipo di grafi è
influenzato dai valori medi, e in media tutti i nodi hanno lo stesso numero di
archi. Questo significa che le persone conoscono le stesse persone, che ogni
neurone si connette allo stesso numero di neuroni, che tutti i siti ricevono lo
stesso numero di visite.
Questa situazione è irrealistica, per questo nelle applicazioni reali si usano
altri tipi di grafo.
\subsection{Distribuzione Power Law (scale-free)}
Le distribuzioni di probabilità più conosciute sono quelle a campana
(Gaussiana), la {\bf Power Law} si differenzia in quanto presente un numero
ridotto di nodi con un grado molto elevato (detti {\bf hub}).\\
Esempio degli aeroporti: pochissimi aeroporti con tantissimi collegamenti (che
{\bf dominano} la rete) e tanti nodi con pochi collegamenti. Questo porta ad una
distribuzione di tipo {\bf coda lunga}, in cui la probabilità di trovare nodi
altamente connessi è bassa ma non nulla. In queste distribuzioni spesso non ha
senso basarsi sul valore medio.\\
\\
\bigskip
La frequenza di un evento varia secondo la potenza di qualche suo attributo:
\begin{equation}
p(k)=c*k^{-\alpha}
\end{equation}
\begin{itemize}
\item $\alpha$ è l'esponente che caratterizza la distribuzione
\item c è una costante di normalizzazione tale che l'area sottostante a p(k) sia
uguale a 1
\item il valore medio della distribuzione è finito solo per valori $\alpha > 2$
\end{itemize}
La curva di una distribuzione power law può essere plottata su scala
logaritmica, in questo caso diventa una linea retta che forma un angolo retto
con l'asse orizzontale del grafico:\\
TODO immagine su slides
\begin{equation}
\log p(k) = \log c * k^{-\alpha} = -\alpha * \log k + \log c
\end{equation}

\section{Small world}
All'interno di una Rete esiste una Componente Gigante, con cui è connessa gran
parte del grafo e con cammini molto brevi è possibile collegare l'intera rete.
\\Esempi pratici di come questi cammini siano brevi sono l'esperimento di
Milgram e il Numero di Erdős.

%In una rete Small World al variare di p si ottengono i seguenti risultati:
%\begin{itemize} 
%\item p = 0 $ \Rightarrow $ Grafo regolare
%\item 0< p < 1 $ \Rightarrow $ Grafo Small Sworld
%\item p = 1  $ \Rightarrow $ Grafo Random 
%\end{itemize}

\subsection{L'esperimento di Milgram}
L'esperimento di Milgram consiste nel verificare la teoria dei sei gradi di
separazione, ovvero un'ipotesi secondo cui qualunque persona può essere
collegata a qualunque altra persona attraverso una catena di conoscenze con non
più di 5 intermediari.\\ Ogni persona che ha partecipato all'esperimento
conosceva il nome del destinatario, la sua occupazione, e la zona in cui
risiedeva, ma non l'indirizzo preciso quindi questi avrebbero dovuto mandare una
lettera ad una persona da loro conosciuta, che a loro giudizio avesse il maggior
numero di possibilità di conoscere il destinatario finale. Quella persona
avrebbe fatto lo stesso, e così via fino a che la lettera non venisse
personalmente consegnato al destinatario finale oppure persa.\\
Il risultato finale è stato che delle lettere consegnate, ovvero 64 su le 296
inviate, la lunghezza media dei percorsi effettuata è esattamente 6.
\subsection {Il numero di Erdős e il numero di Bacon}
{\bf Il numero di Erdős} è un modo per descrivere la "distanza" tra una persona
e il matematico ungherese Paul Erdős in termini di collaborazione in
pubblicazioni matematiche.\\Erdős possiede un numero pari a 0, ogni persona che
vi ha lavorato direttamente invece 1. Allo stesso modo viene assegnato un numero
sempre crescente a persone che hanno lavorato "indirettamente", nel senso che
hanno lavorato con persone che a loro volta hanno lavorato con Erdős.\\\\
Una variante calcola il numero utilizzando Kevin Bacon invece di Erdős come
centro nella rete Small World, e "l'universo" di Holliwood invece di quello
matematico.\\
In entrambi i casi il risultato dell'esperimento è che con numeri molto bassi,
quindi cammini brevi, è possibile rappresentare un numero elevato di
collegamenti.
%\subsection{Il modello di Kleinberg}
%Molto simile a Chord ma con una distribuzione casuale dei finger.

\subsection{I Motori di Ricerca}
I motori di ricerca risolvono il problema della biblioteca priva del
bibliotecario. Attraverso il {\bf Crawling} partendo da un nodo detto {\bf Seme}
si estraggono tuttii collegamenti alle altre pagine vicine, le visite si possono
effettuare sia in ampiezza che in profondità.\\ La scelta del seme è molto
importante, una componente isolata produrrebbe un risulato inferiore. Nella
realtà i crawler vengono eseguiti in maniera distribuita, partendo da semi
diversi e cercando di evitare e al massimo scartare eventuali risultati
duplicati.\bigskip

